home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6020 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.6 KB
  1. Path: newsxfer2.itd.umich.edu!agate!kaskel
  2. From: kaskel@durban.berkeley.edu (Bruce Kaskel)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: 22 Feb 1996 05:57:00 GMT
  6. Organization: U.C. Berkeley Math. Department.
  7. Message-ID: <4gh0jc$6gr@agate.berkeley.edu>
  8. References: <4fr8be$ass@news.iconn.net> <4fvgbu$kmb@winx03.informatik.uni-wuerzburg.de> <TANMOY.96Feb15133510@qcd.lanl.gov> <312A49F0.167E@silk.gsfc.nasa.gov>
  9. NNTP-Posting-Host: durban.berkeley.edu
  10.  
  11. In article <312A49F0.167E@silk.gsfc.nasa.gov>,
  12. Thomas A. McGlynn <tam@silk.gsfc.nasa.gov> wrote:
  13. >If you think about this long enough, it becomes clear that the last digit
  14. >then must be cyclic with a period of no longer than 40.
  15.  
  16. Nope. Don't' forget the factors of 5.
  17.  
  18. >Consider pairs of
  19. >last digits of numbers and their factorials.  The last digit of the factorial
  20. >must be one of 2,4,6,8 (for n>1) so the combination of the last digit of
  21. >n and the last digit of n! must repeat within a cycle of 40 iterations.
  22.  
  23. 8 out of those 40 iterations will add make the last digit 0.
  24.  
  25. >But since the sequence of last digits of n is fixed (ie., 1234567890), and
  26. >we're starting with the same last digit of n!, the last digits of n! must
  27. >repeat.  Thus the function should be writeable in terms of a lookup table
  28.  
  29. When the last digit of n is 5 or 0, you can't tell (by the last digit) how
  30. many factors of 5 divide n. This is why your idea won't work.
  31.  
  32. >No doubt someone else has presented this solution as well.  This problem
  33. >has generated an impressive amount of traffic....
  34. >
  35. >        Tom McGlynn
  36. >            Goddard Space Flight Center
  37. >
  38.  
  39. I find the recursive solution fastest.
  40.  
  41. --Bruce Kaskel
  42.  
  43.